HDU 4631 Sad Love Story(离线思想、分治)

题意:

$N\le 5\times 10^5,给定二维平面上N个点,定义距离为欧氏距离的平方$
$挨个加入每个点,对于i>1的所有点,求[1,i]的最近点对距离,输出这些距离和$

分析:

$考虑离线,倒着做,求一次最近点对,假设得到的点为(p, q),p < q$
$那么显然[q,n]的答案都是dis(p,q)$
$去掉[q,n]这些点,做[1,q-1]的部分,成为子问题$
$由于是随机数据,每次问题规模下降1/3,所以总体复杂度大概是O(nlog^2n)$


$其实还可以直接暴力,挨个添加点到set,设当前答案为d$
$对于每个点,设坐标为(x,y),暴力查询横坐标在[x-d, x+d]范围的点$
$由于随机数据,答案下降的很快,所以跑的飞快$
$时间复杂度大概在O(nlogn)$

第一种解法代码:

  1. //
  2. // Created by TaoSama on 2016-03-18
  3. // Copyright (c) 2016 TaoSama. All rights reserved.
  4. //
  5. #pragma comment(linker, "/STACK:1024000000,1024000000")
  6. #include <algorithm>
  7. #include <cctype>
  8. #include <cmath>
  9. #include <cstdio>
  10. #include <cstdlib>
  11. #include <cstring>
  12. #include <iomanip>
  13. #include <iostream>
  14. #include <map>
  15. #include <queue>
  16. #include <string>
  17. #include <set>
  18. #include <vector>
  19. using namespace std;
  20. #define pr(x) cout << #x << " = " << x << " "
  21. #define prln(x) cout << #x << " = " << x << endl
  22. const int N = 5e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
  23. int n;
  24. typedef pair<int, int> P;
  25. typedef long long LL;
  26. P a[N]; int id[N];
  27. pair<LL, P> dfs(int l, int r) {
  28. if(l == r) return {~0ull >> 2, { -1, -1}};
  29. int m = l + r >> 1;
  30. LL x = a[id[m]].first;
  31. auto ret = min(dfs(l, m), dfs(m + 1, r));
  32. inplace_merge(id + l, id + m + 1, id + r + 1, [](int x, int y) {
  33. return a[x].second < a[y].second;
  34. });
  35. vector<int> v;
  36. for(int i = l; i <= r; ++i) {
  37. int p = id[i];
  38. if((a[p].first - x) * (a[p].first - x) >= ret.first) continue;
  39. for(int j = 0; j < v.size(); ++j) {
  40. int q = v[v.size() - 1 - j];
  41. LL dy = a[p].second - a[q].second;
  42. if(dy * dy >= ret.first) break;
  43. LL dx = a[p].first - a[q].first;
  44. LL d = dx * dx + dy * dy;
  45. if(d < ret.first) ret = {d, {p, q}};
  46. }
  47. v.push_back(p);
  48. }
  49. return ret;
  50. }
  51. int main() {
  52. #ifdef LOCAL
  53. freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
  54. // freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
  55. #endif
  56. ios_base::sync_with_stdio(0);
  57. int t; scanf("%d", &t);
  58. while(t--) {
  59. scanf("%d", &n);
  60. int a1, b1, c1, a2, b2, c2;
  61. scanf("%d%d%d", &a1, &b1, &c1);
  62. scanf("%d%d%d", &a2, &b2, &c2);
  63. for(int i = 1; i <= n; ++i) {
  64. a[i].first = (1LL * a1 * a[i - 1].first + b1) % c1;
  65. a[i].second = (1LL * a2 * a[i - 1].second + b2) % c2;
  66. }
  67. LL ans = 0;
  68. for(int r = n; r > 1;) {
  69. for(int i = 1; i <= r; ++i) id[i] = i;
  70. sort(id + 1, id + 1 + r, [](int x, int y) {
  71. return a[x] < a[y];
  72. });
  73. auto cp = dfs(1, r);
  74. int nxt = max(cp.second.first, cp.second.second);
  75. ans += cp.first * (r - nxt + 1);
  76. r = nxt - 1;
  77. }
  78. printf("%I64d\n", ans);
  79. }
  80. return 0;
  81. }